package com.yangli.ahies.study;

/**
 * @author ly
 * @description
 * @data 2021/8/31
 */
public class A {

    /*
    * 3. 数组中重复的数字
    *在一个长度为 n 的数组里的所有数字都在 0 到 n-1 的范围内。数组中某些数字是重复的，但不知道有几个数字是重复的，也不知道每个数字重复几次。请找出数组中任意一个重复的数字。
    Input:
    {2, 3, 1, 0, 2, 5}
    Output:
    2
    *
    *
    * 要求时间复杂度 O(N)，空间复杂度 O(1)。因此不能使用排序的方法，也不能使用额外的标记数组。
    对于这种数组元素在 [0, n-1] 范围内的问题，可以将值为 i 的元素调整到第 i 个位置上进行求解。在调整过程中，如果第 i 位置上已经有一个值为 i 的元素，就可以知道 i 值重复。
    * */

    public int duplicate1(int[] nums) {
        if (nums == null || nums.length == 0) {
            return -1;
        }
        for (int i = 0, j = nums.length; i < j; i++) {
            while (nums[i]!=i){
                if(nums[i]==nums[nums[i]]){
                    return  nums[i];
                }
                swap(nums,i,nums[i]);
            }
        }
        return -1;

    }

    public int duplicate (int[] numbers) {
        int[] arr = new int[numbers.length];
        for(int i=0;i<numbers.length;i++){
            if(++arr[numbers[i]] == 2 ){
                return numbers[i];
            }
        }
        return -1;
    }


    private void swap(int[] nums,int i,int j){
       int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }

}
